package com.explorati.LeetCode070.climbingstairs;

/**
 * 70. Climbing Stairs
 * 
 * You are climbing a stair case. It takes n steps to reach to the top.
 * 
 * Each time you can either climb 1 or 2 steps. In how many distinct ways can
 * you climb to the top?
 * 
 * Input: 2 Output: 2
 * 
 * Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2
 * steps
 * 
 * @author explorati
 *
 */
public class Solution {
	public int climbStairs(int n) {
		int[] memo = new int[n + 1];
		memo[0] = 1;
		memo[1] = 1;

		for (int i = 2; i < n + 1; i++) {
			memo[i] = memo[i - 1] + memo[i - 2];
		}
		return memo[n];

		// if(n == 0){
		// return 1;
		// }
		// if(n == 1){
		// return 1;
		// }
		// return climbStairs(n - 1) + climbStairs(n - 2);
	}
}
